/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    pair<ListNode*, ListNode*> reverse(ListNode* head, ListNode* pre, int k) {
        if (head == nullptr)
            return {nullptr, nullptr};
        if (head->next == nullptr)
            return {nullptr, nullptr};
        ListNode* l1 = head;
        int count = 0;
        while (l1) {
            ++count;
            l1 = l1->next;
        }
        if (count < k)
            return {nullptr, nullptr};
        --k;
        ListNode *prev = head, *cur = head->next, *_next = head->next->next;
        while (k--) {
            cur->next = prev;
            while (prev->next != cur)
                prev = prev->next;
            prev->next = _next;
            prev = cur;
            cur = _next;
            if(_next) _next = _next->next;
        }
        if (pre)
            pre->next = prev;
        return {prev, cur};
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (k == 1)
            return head;
        auto t = reverse(head, nullptr, k);
        head = t.first;
        ListNode* phead = t.second;
        ListNode* pre = t.first;
        while (pre->next != phead)
            pre = pre->next;
        while (phead) {
            auto p = reverse(phead, pre, k);
            phead = p.second;
            pre = p.first;
            while (pre && pre->next != phead)
                pre = pre->next;
        }
        return head;
    }
};